﻿#define _CRT_SECURE_NO_WARNINGS  1
//一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
//一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考
#include"Sort.h"



void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
void STDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("relloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
bool STEMpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}







//插入排序
void InsertSort(int* p, int size)
{
	assert(p);
	//[0 end]有序，将end+1插入保持end+1有序
	for (int i = 0; i < size - 1; i++)
	{
		int end = i;
		int tmp = p[end + 1];
		while (end >= 0)
		{
			if (p[end] > tmp)
			{
				p[end + 1] = p[end];
			}
			else {
				break;
			}
			end--;
		}
		p[end + 1] = tmp;
	}
}
//打印函数
void PrintSort(int* p, int size)
{
	assert(p);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", p[i]);
	}
	printf("\n");
}
//交换函数
void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//希尔排序
void ShellSort(int* p, int size)
{
	int gap = size;
	while (gap >1)//一个数/2最终必然会等于1
	{
		gap = gap / 2;
		for (int i = 0; i < size - gap; i++)
		{
			int end = i;
			int tmp = p[end + gap];
			while (end >= 0)
			{
				if (p[end] > tmp)
				{
					//向后调整
					p[end + gap] = p[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			//将数据插入到end+gap位置上
			p[end + gap] = tmp;
		}
	}
}
//冒泡排序
void BubbleSort(int* p, int size)
{
	assert(p);
	for (int j = 0; j < size; j++)
	{
		for (int i = 1; i < size-j; i++)
		{
			if (p[i - 1] > p[i])
			{
				swap(&p[i - 1], &p[i]);
			}
		}
	}
}
void Adjustdown(int* p, int n, int parent)
{
	assert(p);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && p[child + 1] > p[child])
		{
			child++;
		}
		if (p[child] > p[parent])
		{
			swap(&p[child], &p[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
//堆排序
void HeapSort(int* n, int size)
{
	assert(n);
	//向下调整建堆(建大堆）
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown(n, size, i);
	}


	//排升序   向下调整堆(n*logn)
	int end = size - 1;
	while (end > 0)
	{
		swap(&n[0], &n[end]);
		Adjustdown(n, end, 0);//（注意传参）
		end--;
	}

}
//选择排序
void select(int* p, int size)
{
	assert(p);
	/*int begin = 0, end = size - 1;
	while (begin < end)
	{
		int max = begin, min = begin;
		for (int i = begin + 1; i < end; i++)
		{
			if (p[i] > p[max])
			{
				max = i;
			}
			if (p[i] < p[min])
			{
				min = i;
			}
		}
		swap(&p[begin], &p[min]);
		if (max == begin)
		{
			max = min;
		}
		swap(&p[end], &p[max]);
		end--;
		begin++;
	}*/
















	int begin = 0;
	int end = size - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin+1; i <= end; i++)//注意i的取值范围
		{
			if (p[i] < p[mini])
			{
				mini = i;
			}
			if (p[i] > p[maxi])
			{
				maxi = i;
			}
		}
		swap(&p[mini], &p[begin]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		swap(&p[maxi], &p[end]);
		--end;
		++begin;
	}
}
//三数取中
int ThreeMid(int* p, int left, int right)
{
	int mid = (left + right) / 2;
	if (p[left] < p[mid])
	{
		if (p[mid] < p[right])
		{
			return mid;
		}
		else if (p[left] > p[right])
		{
			return left;
		}
		else
			return right;
	}
	else//p[left]>p[mid]
	{
		if (p[mid] > p[right])
		{
			return mid;
		}
		else if (p[left] < p[right])
		{
			return left;
		}
		else
			return right;
	}

}
//前后指针法
int PointerSort3(int* p, int left, int right)
{
	int mid = ThreeMid(p, left, right);
	swap(&p[mid], &p[left]);
	int prve = left;
	int cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		//cur找小
		if (p[cur] < p[key] && ++prve != cur)
		{
			swap(&p[cur], &p[prve]);
		}
		cur++;
	}
	swap(&p[prve], &p[key]);
	return prve;
}
//hoare版本
int PartSort1(int* p, int left, int right)
{
	/*int mid = ThreeMid(p, left, right);
	swap(&p[mid], &p[left]);*/
	int key = left;
	while (left<right)
	{
		//右边先走，找小的，
		while (left < right && p[right] >= p[key])
		{
			right--;
		}
		//左边找大的，
		while (left < right && p[left] <= p[key])
		{
			left++;
		}
		swap(&p[left], &p[right]);
	}
	swap(&p[key], &p[left]);
	return left;
}
//挖坑法
int  PartSort2(int* p, int left, int right)
{
	int mid = ThreeMid(p,left,right);
	swap(&p[mid], &p[left]);
	int key = p[left];
	int hole = left;
	while (left < right)
	{
		//先右边先走，找小，填到左边去，右边形成新的坑位
		while (left < right && p[right] >= key)
		{
			right--;
		}
		p[left] = p[right];
		hole = right;
		//左边找大，填到右边去，左边形成新的坑位
		while (left < right && p[left] <= key)
		{
			left++;
		}
		p[right] = p[left];
		hole = left;
	}
	p[hole] = key;
	return hole;
}
void QuickSort(int* p, int begin, int end)
{
	if (begin >= end)
	{
		return ;
	}
	int mid = PartSort1(p, begin, end);
	//[begin,mid-1] mid [mid+1,end]
	//QuickSort(p, begin, mid - 1);
	//QuickSort(p, mid + 1, end);
}
//快排非递归实现
void QuickSort2(int* p, int begin, int end)
{
	//通过栈来实现
	ST st;
	STInit(&st);
	STPush(&st,end);
	STPush(&st,begin);
	while (!STEMpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);
		int key = PartSort1(p, left, right);
		//[left key-1] key [key+1 right]
		
		if (key+1< right)
		{
			STPush(&st, right);
			STPush(&st, key + 1);
		}
		if (left < key - 1)
		{
			STPush(&st, key - 1);
			STPush(&st, left);
		}
	}
	STDestory(&st);
}
void _MergeSort(int* p, int* tmp, int begin, int end)
{
	//分为两步，第一步分解，第二步合并
    //第一步分解
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	//[begin mid][mid+1 end]
	_MergeSort(p, tmp, begin, mid);
	_MergeSort(p, tmp, mid + 1, end);
	//第二步合并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int mark = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (p[begin1] < p[begin2])
		{
			tmp[mark++] = p[begin1++];
		}
		else
		{
			tmp[mark++] = p[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[mark++] = p[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[mark++] = p[begin2++];
	}
	memcpy(p + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//归并排序(空间复杂度较高   O(n) 递归实现)
void MergeSort(int* p, int size)
{
	int* tmp = (int*)malloc(size * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	_MergeSort(p, tmp, 0, size - 1);
	free(tmp);
}
//归并排序（非递归实现）
void MergeSort2(int* p, int size)
{
	//开辟一个存储空间
	int* tmp = (int*)malloc(sizeof(int) * size);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	int gap = 1;
	while (gap < size)
	{
		for (int i = 0; i < size; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap * 2 - 1;
			int mark = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (p[begin1] < p[begin2])
				{
					tmp[mark++] = p[begin1++];
				}
				else
				{
					tmp[mark++] = p[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[mark++] = p[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[mark++] = p[begin2++];
			}
			memcpy(p + i, tmp + i, (end2-i+1) * sizeof(int));
		}
		gap *= 2;
	}
	free(tmp);
}
//计数排序
void CuntSort(int* p, int size)
{
	//第一步找出值的范围
	int max = p[0], min = p[0];
	for (int i = 0; i < size; i++)
	{
		if (p[i] > max)
		{
			max = p[i];
		}
		if (p[i] < min)
		{
			min = p[i];
		}
	}
	int range = max - min + 1;
	int* tmp = (int*)malloc(sizeof(int) * range);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	memset(tmp, 0, sizeof(int) * range);
	//统计各个数出现的次数
	for (int i = 0; i < size; i++)
	{
		tmp[p[i] - min]++;
	}
	//排序
	int mark = 0;
	for (int i = 0; i < range; i++)
	{
		while (tmp[i]--)
		{
			p[mark++] = i + min;
		}
	}
	//第一步找值的范围
	//int max = p[0], min = p[0];
	//for (int i = 0; i < size; i++)
	//{
	//	if (p[i] < min)
	//	{
	//		min = p[i];
	//	}
	//	if (p[i] > max)
	//	{
	//		max = p[i];
	//	}
	//}
	//int range = max - min - 1;
	////建数组
	//int* count = (int*)malloc(sizeof(int) * range);
	//if (count == NULL)
	//{
	//	perror("malloc fail");
	//	exit(-1);
	//}
	//memset(count, 0, sizeof(int) * range);
	////统计数据出现的次数
	//for (int i = 0; i < size; i++)
	//{
	//	count[p[i] - min]++;
	//}
	////排序
	//int mark = 0;
	//for (int i = 0; i < range; i++)
	//{
	//	while (count[i]--)
	//	{
	//		p[mark++] = i + min;
	//	}
	//}
}